package com.company.堆栈队列;

import java.util.*;

/**
 * @author Administrator
 */
public class 滑动窗口的最大值 {
    public ArrayList<Integer> maxInWindows1(int[] num, int size) {

        /**
         * 第一种方法：栈的知识点
         *   用栈的知识点算法复杂度太高
         */

        Stack<Integer> stack = new Stack<>();
        ArrayList<Integer> result = new ArrayList<>();

        for (int i = 0; i < num.length - size + 1; i++) {
            int k = 1;
            for (int j = i; j <= num.length; j++) {
                if (k <= size) {
                    stack.push(num[j]);
                    k++;
                } else {
                    int max = 0;
                    while (!stack.isEmpty()) {
                        Integer pop = stack.pop();
                        if (max < pop) {
                            max = pop;
                        }
                    }
                    result.add(max);
                    break;
                }
            }
        }
        return result;
    }

    /**
     * 第二种方法：大根堆，双层循环复杂度还是很高
     *
     * @param num
     * @param size
     * @return
     */
    public ArrayList<Integer> maxInWindows2(int[] num, int size) {
        PriorityQueue<Integer> queue = new PriorityQueue<>((o1, o2) -> o2.compareTo(o1));
        ArrayList<Integer> result = new ArrayList<Integer>();
        if (num.length == 0 || size == 0) {
            return result;
        }
        for (int i = 0; i < num.length - size + 1; i++) {
            for (int j = i; j <= i + size - 1; j++) {
                queue.offer(num[j]);
            }
            result.add(queue.peek());
            queue.clear();
        }
        return result;
    }

    /**
     * 第三种方法：大根堆，去掉双层循环
     *
     * @param num
     * @param size
     * @return
     */
    public ArrayList<Integer> maxInWindows3(int[] num, int size) {
        PriorityQueue<Integer> requeue = new PriorityQueue<>((o1, o2) -> o2.compareTo(o1));
        ArrayList<Integer> result = new ArrayList<Integer>();
        for (int i = 0; i < size; i++) {
            requeue.offer(num[i]);
        }
        int index = 0;
        for (int i = size; i < num.length; i++) {
            result.add(requeue.peek());
            requeue.remove(num[index]);
            requeue.offer(num[i]);
            index++;
        }
        result.add(requeue.peek());
        return result;
    }

    public static void main(String[] args) {
        int[] list = {2, 3, 4, 2, 6, 2, 5, 1};
        int size = 3;
        滑动窗口的最大值 s = new 滑动窗口的最大值();
        ArrayList<Integer> integers = s.maxInWindows1(list, size);
        System.out.println(integers);

        List<Integer> resList = new ArrayList<>();
        int index = 0;
        PriorityQueue<Integer> priority = new PriorityQueue<>((o1, o2) -> o2.compareTo(o1));
        for (int i = 0; i < size; i++) {
            priority.offer(list[i]);
        }

        for (int i = size; i < list.length; i++) {
            resList.add(priority.peek());
            priority.remove(list[index]);
            priority.offer(list[i]);
            index++;
        }
        resList.add(priority.peek());
        System.out.println(resList);
    }
}
